// Package _3_I_在排序数组中查找数字I main
// @Title _3_I_在排序数组中查找数字I
// @Description  统计一个数字在排序数组中出现的次数。
// @Author  == 琳琳也叫王木木 ==  2022-01-16 18:10
// @Create  2022-01-16 18:10
package main

import "fmt"

/**
 当然了，最简单的是使用哈希表统计嘛 没难度

 但是排序数组，我们可以使用二分查找

	当然双指针也可以
*/

func main() {
	nums := []int{5, 7, 7, 8, 8, 10}
	//fmt.Println(search(nums,8))
	fmt.Println(searchTP(nums, 6))
}

//
//  search
//  @Description: 使用二分查找的方式求排序数组中出现的次数  其实效率不如双指针
//  @param nums：
//  @param target：
//  @return int：
//
func search(nums []int, target int) int {
	if len(nums) == 0 {
		return 0
	}
	// 最大的问题就是找到第一个等于target的下标和最后一个等于target的下标
	lIndex := binarySearch(nums, target, true)
	rIndex := binarySearch(nums, target, false) - 1
	if lIndex <= rIndex && rIndex < len(nums) && nums[lIndex] == target && nums[rIndex] == target {
		return rIndex - lIndex + 1
	}
	return 0
}

func binarySearch(nums []int, target int, lower bool) int {
	l, r, a := 0, len(nums)-1, len(nums)
	for l <= r {
		mid := l + (r-l)>>2
		if nums[mid] > target || (nums[mid] >= target && lower) {
			r = mid - 1
			a = mid
		} else {
			l = mid + 1
		}
	}
	return a
}

func searchTP(nums []int, target int) int {
	if len(nums) == 0 {
		return -1
	}
	l, r := 0, len(nums)-1
	for l <= r {
		if nums[l] == target && nums[r] == target {
			break
		}
		if nums[l] < target {
			l++
		}
		if nums[r] > target {
			r--
		}
	}
	// 最大的问题就是找到第一个等于target的下标和最后一个等于target的下标
	return r - l + 1
}
